package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-palindromic-substring/
 * @create 2025/8/29 16:22
 * @since JDK17
 */

public class Solution19 {
    static int[][] dp = new int[1001][1001];
    public int f(char[] s, int l, int r) {
        if (l == r) {
            return 1;
        }
        if (l == r - 1) {
            return s[l] == s[r] ? 2 : 1;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        int ans = 0;
        if (s[l] == s[r]) {
            ans = f(s, l + 1, r - 1) + 2;
        } else {
            ans = Math.max(f(s, l + 1, r), f(s, l, r - 1));
        }
        return dp[l][r] = ans;
    }

    public int longestPalindromeSubseq(String str) {
        char[] s = str.toCharArray();
        for (int i = 0; i < s.length; i++) {
            Arrays.fill(dp[i], 0, s.length, -1);
        }
        return f(s, 0, s.length - 1);
    }
}
